package leetcode.lcp0033;

import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int storeWater(int[] bucket, int[] vat) {
		int add = 0;// 加水次数
		int len = vat.length;
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[2] == a[2] ? a[0] - b[0] : b[2] - a[2]);
		for (int i = 0; i < len; i++) {
			if (bucket[i] == 0 && vat[i] != 0) {// ?
				add++;
				bucket[i] = 1;
			}
			if (vat[i] != 0) {
				int times = (vat[i] + bucket[i] - 1) / bucket[i];
				queue.add(new int[] { bucket[i], vat[i], times });
			}
		}
		if (queue.isEmpty()) {//
			return 0;
		}
		int max = queue.peek()[2];
		int ans = add + max;
		while (!queue.isEmpty() && max >= 0) {
			int[] cur = queue.poll();
			int ifAdd1 = (cur[1] + cur[0]) / (cur[0] + 1);
			int next = queue.isEmpty() ? 0 : queue.peek()[2];
			int curAns = ++add + Math.max(ifAdd1, next);
			queue.add(new int[] { cur[0] + 1, cur[1], ifAdd1 });
			ans = Math.min(curAns, ans);
			max--;
		}
		return ans;
	}

	@Override
	public void debug4() {
		HelpDebug.compare(633, this.storeWater(HelpDebug.str2array3("[0,0,0,0,0,0,0,0,0,0]"),
				HelpDebug.str2array3("[10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]")));
		HelpDebug.compare(4, this.storeWater(HelpDebug.str2array3("[1,3]"), HelpDebug.str2array3("[6,8]")));
		HelpDebug.compare(0, this.storeWater(HelpDebug.str2array3("[3,2,5]"), HelpDebug.str2array3("[0,0,0]")));
		HelpDebug.compare(2, this.storeWater(HelpDebug.str2array3("[0]"), HelpDebug.str2array3("[1]")));
		HelpDebug.compare(3, this.storeWater(HelpDebug.str2array3("[9,0,1]"), HelpDebug.str2array3("[0,2,2]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

//	[0,0,0,0,0,0,0,0,0,0]
//			[10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]

//	[9988,5017,5130,2445,9896,9151,3625,7801,608,3283,1386,979,5209,4182,8234,9870,8714,6435,3800,956,4006,5620,7474,1205,6993,3320,1201,7593,905,3816,4522,4560,8027,8219,6686,3779,2141,1240,6504,6612,6921,7329,8145,5745,7652,4340,7933,6246,5157,9447,107,9665,3653,2978,9832,4945,4312,2199,449,8432,3230,8163,800,6547,1110,1194,9384,632,3275,1229,7230,8643,7613,8256,5043,1288,3088,8997,4554,4755,7433,8146,9722,3469,8863,5831,7816,5058,4316,7946,8402,975,2450,4958,9811,9336,21,9309,8999,56]
//			[9991,6973,7192,9876,9910,9549,3700,8814,1308,9981,9234,7292,7732,8458,8441,9939,9621,7285,7452,2718,6589,7555,8788,3202,7832,4781,8798,9299,2112,9963,8755,7240,9217,8587,6782,9703,8954,3759,6907,7218,7333,8020,8323,5750,9510,8571,8664,8510,9363,9741,8643,9825,4227,8530,9961,8511,8949,7486,9086,9690,5316,9581,9314,8817,7234,8998,9485,5394,7365,1501,7984,9802,9778,8314,7482,7117,5117,9609,8732,9728,9330,8800,9775,6210,8966,7700,8802,7607,8950,9730,9855,1231,5228,5329,9982,9532,3230,9951,9034,8299]

}
